package correct.day21;

import java.util.Scanner;

public class Test3 {
    // 1. 状态表⽰： dp[i][j] 表⽰：字符串 [i, j] 范围内的最⻓回⽂⼦序列的⻓度；
    // 2. 状态转移⽅程：
    //  ◦ 当 i == j 的时候，只有⼀个字符，⻓度为 1;
    //  ◦ 当 i < j 的时候，分情况讨论：
    //   ▪ s[i] == s[j]：dp[i][j] = dp[i + 1][j - 1];
    //   ▪ s[i] != s[j]：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])；
    // 3. 返回值： dp[0][n - 1] 。
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        char[] s = in.next().toCharArray();
        int n = s.length;
        int[][] dp = new int[n][n];
        for(int i = n - 1; i >= 0; i--)
        {
            dp[i][i] = 1;
            for(int j = i + 1; j < n; j++)
            {
                if(s[i] == s[j])
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                else
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
        System.out. println(dp[0][n - 1]);
    }
}
